#include <stdio.h>
#include <stdlib.h>

#define BUFF_SIZE 10 
int data[BUFF_SIZE] = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10};

typedef struct node
{
	int data;
	struct node *next;	

}node, Node;

node* create_head (void)
{
	node *head;

	head = (node *)malloc (sizeof (node));
	if (head == NULL)
	{
		printf ("Out of space");
		return NULL;
	}
	else
	{
		head->data = 999;
		head->next = NULL;
	}

	return head;
}

node* create_list (node *head, int *data, int length)
{
	int i;
	node *n, *temp;

	temp = head;
	
	for (i=0; i<length; i++)
	{
		n = (node *)malloc (sizeof (node));
		if (n == NULL)
		{
			printf ("outof space");
			return NULL;
		}
		else
		{
			n->data = data[i];
			n->next = NULL;
			temp->next = n;
			temp = temp->next;
		}
	}
	return head;
}

void print_list (node *head)
{
	int i;
	node *temp;
	
	temp = head->next;
	do
	{
		printf ("%d\t", temp->data);
		temp = temp->next;
	}while (temp->next != NULL);

	printf ("%d\n", temp->data);
}

node *find_pos (node *head, int f)
{
	node *temp;
	
	temp = head;
	while (temp->next != NULL && temp->data != f)
	{
		temp = temp->next;
	}
	return temp;
}

node *insert_element (node *head, int ins, int pos)
{
	node *temp, *n, *p;

	temp = head;
	
//	do
//	{
		n = (node *)malloc (sizeof (node));
		if (n == NULL)
		{
			printf ("Out of space");
			return NULL;
		}
		else
		{
			n->data = ins;
			//n->next = NULL;
			
			p = find_pos (head, pos);		
			if (p->data != pos)
				printf ("%d position element is not in the list, so inserting at end of the list\n", pos);
			n->next = p->next;
			p->next = n; 
			
		}
//	}
	
	return head;
}


node *find_prev (node *h, int num)
{
	node *temp;

	temp = h;
	while (temp ->next != NULL && temp->next->data != num)
	{
		temp = temp->next;
	}
	return temp;
}


node *del_list (node *head, int d)
{
	node *temp, *prev;

	prev = find_prev (head, d);
	temp = prev->next;
	prev->next = temp->next;

	return head;
}

Node * reverse (Node * n)
{
	Node * result = n;
	
	if (n -> next != NULL)
	{
		result = reverse (n -> next);
		n -> next -> next = n;
	}
	
	return result;
}
 
Node * reverse2 (Node * n)
{
	Node * result = reverse (n);
	
	n -> next = NULL; // Because n is now the last node in the list
	
	return result;
}

node *reverse_non_recurcive(Node *p) 
{ 
	Node *pr = NULL; 
	while (p != NULL) 
	{ 
		Node *tmp = p->next; 
		p->next = pr; 
		pr = p; 
		p = tmp; 
	} 
	return pr; 

} 

node* reverse_non_recurcive2 (node* head) 
{ 
  node* next; 
  node* prev=NULL; 
  node* curr=head; 

  if(!head) return head; 
  while(curr->next != NULL) 
  { 
    next=curr->next; 
    curr->next=prev; 
    prev=curr; 
    curr=next; 
  }   
  // This is required else the last node pointer is left dangling. 
  curr->next=prev; 
   
  return curr; 

} 

Node* reverse_non_recurcive3 (Node * head )
 {
          Node * temp = NULL ;
          Node * np = NULL;
        
        while (head)
          {
           temp = head->next;
           head->next = np;
           np = head ;
           head = temp;     
        
          }
          return np ;
            
 }

Node * reverse_non_recurcive4(Node *Head)
{
	Node *prev_ptr, *cur_ptr, *temp;

	cur_ptr=Head; 
	prev_ptr=NULL;

	while(cur_ptr != NULL)  
	{ 
		temp=prev_ptr; 
		prev_ptr=cur_ptr; 

		cur_ptr=cur_ptr->next; 
		prev_ptr->next=temp;  
	}  

	Head=prev_ptr;  

	return Head;
} 

node *reverse_non_recurcive5 (node *head)
{
     node* result = NULL;
     node* current;
     node* next;
	
	current = head;

     while(current != NULL)
     {
        next = current->next;
        current->next = result;
        result = current;

        current = next;
     }     
     head = result;
	
	return head;
}


node *sortNodes(Node * ptr) 
{
	Node * temp = ptr;
	Node * curr;
	int didSwap;
	for(didSwap = 1; didSwap; ) 
	{
		didSwap = 0;
		for(curr = ptr; curr->next != NULL; curr = curr->next) 
		{
			if(curr->data > curr->next->data) 
			{
				temp->data = curr->data;
				curr->data = curr->next->data;
				curr->next->data = temp->data;
				didSwap = 1;
			} 
		}
	}
	return ptr;
}

main ()
{
	node *h, *p;		
	int i, e, pos, del, ch=0;
	
	printf ("Single Linked List - C Program source code\n");	

	h = create_head();

	while (ch != 7)
	{
	printf ("\n1-create list\n2-print list\n3-insert new element\n4-delete\n5-reverse\n6-sort\n7-Quit\nenter your choice...\t");
	scanf ("%d", &ch);

	switch (ch)
	{
		case 1:	
			h = create_list (h, data, BUFF_SIZE);
			break;
		case 2:
			print_list(h);
			break;
		case 3:
			printf ("enter the num to insert\t");
			scanf ("%d", &e);
			printf ("\nafter which element you want to insert ?\t");
			scanf ("%d", &pos);
			h = insert_element (h, e, pos);
			break;
	
		case 4:
			printf ("\nenter the num to delete from list\t");
			scanf ("%d", &del);
			h = del_list (h, del);	
			break;
	
		case 5:
//			h = reverse2(h);
//			h = reverse_non_recurcive (h);
//			h = reverse_non_recurcive2 (h);
//			h = reverse_non_recurcive4 (h);
			h = reverse_non_recurcive5 (h);
			break;		

		case 6:
			h = sortNodes (h);
			break;
		
		default:
			printf ("\nenter correct choice...\n");
			break;
			
	}
	}
}
